import random


class OtherSort:
    @staticmethod
    def shuffle_sort(arr):
        """
        混排（Shuffle Sort）算法的核心思想是通过随机交换数组中的元素来达到排序的目的。

        参数：
        arr (list): 待排序的列表。

        返回：
        list: 排序后的列表。

        稳定性：
        不是稳定排序算法。
        原因：混排中，相同元素的相对顺序可能会改变。
        """

        # 步骤 1: 对数组进行多次随机交换
        n = len(arr)
        for i in range(n-1):
            j = random.randint(0, i)
            arr[i], arr[j] = arr[j], arr[i]

        # 步骤 2: 返回交换后的数组作为排序结果
        return arr

    @staticmethod
    def sleep_sort(arr):
        """
        睡眠排序Sleep Sort算法的核心思想是根据数组中的元素值创建多个线程 并通过线程睡眠的时间来实现排序。

        参数：
        arr (list): 待排序的列表。

        返回：
        list: 排序后的列表。

        稳定性：
        是稳定排序算法。
        原因：睡眠排序中，相同元素的相对顺序不会改变。
        """
        import threading
        import time
        def _sleep_and_append(num, sorted_list):
            """
            线程执行的函数，设置睡眠时间为当前元素的值，然后将元素添加到排序结果列表中。

            参数：
            num (int): 当前元素的值。
            sorted_list (list): 排序结果列表。
            """
            time.sleep(num)
            sorted_list.append(num)

        # 步骤 1: 创建一个列表，用于存放排序后的元素
        sorted_list = []

        # 步骤 2: 遍历输入列表中的每个元素，为每个元素创建一个线程
        threads = []
        for num in arr:
            thread = threading.Thread(target=_sleep_and_append, args=(num, sorted_list))
            threads.append(thread)

        # 步骤 3: 在每个线程中，设置睡眠时间为当前元素的值，然后将元素添加到排序结果列表中
        for thread in threads:
            thread.start()

        # 步骤 4: 启动所有线程，等待所有线程执行完成
        for thread in threads:
            thread.join()

        # 步骤 5: 返回排序结果列表
        return sorted_list

    @staticmethod
    def cycle_sort(arr):
        """
        环排序Cycle Sort算法的核心思想是通过不断找到每个元素在数组中的正确位置来实现排序。

        参数：
        arr (list): 待排序的列表。

        返回：
        list: 排序后的列表。

        稳定性：
        是稳定排序算法。
        原因：环排序中，相同元素的相对顺序不会改变。
        """

        # 步骤 1: 遍历输入列表中的每个元素，找到该元素在数组中的正确位置
        n = len(arr)
        for i in range(n - 1):
            item = arr[i]
            pos = i
            for j in range(i + 1, n):
                if arr[j] < item:
                    pos += 1

            # 步骤 2: 将当前元素放到正确位置，并将被替换的元素继续放到它的正确位置
            while item == arr[pos]:
                pos += 1
            arr[pos], item = item, arr[pos]

            # 步骤 3: 重复步骤 1 和 2，直到所有元素都放到了正确位置
            while pos != i:
                pos = i
                for j in range(i + 1, n):
                    if arr[j] < item:
                        pos += 1

                while item == arr[pos]:
                    pos += 1
                arr[pos], item = item, arr[pos]

        return arr

    @staticmethod
    def cocktail_sort(arr):
        """
        鸡尾酒排序（Cocktail Sort）算法的核心思想是通过多次往返扫描来逐步将最大值和最小值放到正确的位置。

        参数：
        arr (list): 待排序的列表。

        返回：
        list: 排序后的列表。

        稳定性：
        是稳定排序算法。
        原因：鸡尾酒排序中，相同元素的相对顺序不会改变。
        """

        # 步骤 1: 初始化左右边界指针
        left, right = 0, len(arr) - 1

        while left < right:
            # 步骤 2: 循环扫描，先从左到右找到最大值并放到正确位置
            for i in range(left, right):
                if arr[i] > arr[i + 1]:
                    arr[i], arr[i + 1] = arr[i + 1], arr[i]

            # 步骤 2: 循环扫描，然后从右到左找到最小值并放到正确位置
            for i in range(right - 1, left - 1, -1):
                if arr[i] > arr[i + 1]:
                    arr[i], arr[i + 1] = arr[i + 1], arr[i]

            # 步骤 3: 缩小边界指针范围
            left += 1
            right -= 1

        return arr


    @staticmethod
    def comb_sort(arr):
        """
        梳排序（Comb Sort）算法是改进版的冒泡排序算法，通过逐步减小比较元素之间的距离来提高排序效率。

        参数：
        arr (list): 待排序的列表。

        返回：
        list: 排序后的列表。

        稳定性：
        是稳定排序算法。
        原因：梳排序中，相同元素的相对顺序不会改变。

        实现步骤：
        1. 初始化间隔大小为数组长度，并设置已交换标志。
        2. 根据间隔大小进行比较并交换元素，直到遍历完整个数组。
        3. 缩小间隔大小，重复步骤 2，直到间隔大小为 1。

        示例：
        >>> input_list = [9, 3, 7, 5, 1, 8, 2, 6, 4, 0]
        >>> sorted_list = CombSort.comb_sort(input_list)
        >>> sorted_list
        # 根据具体实现的算法，输出排序结果
        """

        # 步骤 1: 初始化间隔大小为数组长度，并设置已交换标志
        gap = len(arr)
        swapped = True

        while gap > 1 or swapped:
            # 步骤 2: 根据间隔大小进行比较并交换元素，直到遍历完整个数组
            gap = max(1, int(gap / 1.3))  # 步骤 3: 缩小间隔大小，重复步骤 2，直到间隔大小为 1。
            swapped = False

            for i in range(len(arr) - gap):
                if arr[i] > arr[i + gap]:
                    arr[i], arr[i + gap] = arr[i + gap], arr[i]
                    swapped = True

        return arr

    @staticmethod
    def bogo_sort(arr):
        """
        计算机科学家排序（Bogo Sort）算法的核心思想是通过随机打乱数组顺序来达到排序的目的，直到数组有序为止。

        参数：
        arr (list): 待排序的列表。

        返回：
        list: 排序后的列表。

        稳定性：
        不是稳定排序算法。
        原因：计算机科学家排序中，相同元素的相对顺序可能会改变。

        实现步骤：
        1. 判断数组是否有序，若有序则返回结果，否则进行下一步。
        2. 随机打乱数组顺序。
        3. 重复步骤 1 和 2，直到数组有序为止。

        示例：
        >>> input_list = [9, 3, 7, 5, 1, 8, 2, 6, 4, 0]
        >>> sorted_list = BogoSort.bogo_sort(input_list)
        >>> sorted_list
        # 根据具体实现的算法，输出排序结果
        """
        def _is_sorted(arr):
            """
            判断数组是否有序。

            参数：
            arr (list): 待判断的列表。

            返回：
            bool: 是否有序。
            """
            for i in range(1, len(arr)):
                if arr[i] < arr[i - 1]:
                    return False
            return True

        # 步骤 1: 判断数组是否有序，若有序则返回结果，否则进行下一步
        while not _is_sorted(arr):
            # 步骤 2: 随机打乱数组顺序
            random.shuffle(arr)

        return arr


    @staticmethod
    def bucket_sort(arr):
        """
        木桶排序（Bucket Sort）算法的核心思想是将待排序的元素划分到不同的木桶中，然后对每个木桶中的元素进行排序，最后将所有木桶中的元素合并起来。

        参数：
        arr (list): 待排序的列表。

        返回：
        list: 排序后的列表。

        稳定性：
        是稳定排序算法。
        原因：木桶排序中，相同元素的相对顺序不会改变。
        """

        # 步骤 1: 创建足够数量的木桶
        max_val = max(arr)
        min_val = min(arr)
        num_buckets = len(arr)
        buckets = [[] for _ in range(num_buckets)]

        # 步骤 2: 将待排序的元素划分到不同的木桶中
        for num in arr:
            index = int((num - min_val) / (max_val - min_val) * (num_buckets - 1))
            buckets[index].append(num)

        # 步骤 3: 对每个木桶中的元素进行排序
        for bucket in buckets:
            bucket.sort()

        # 步骤 4: 合并所有木桶中的元素
        sorted_list = []
        for bucket in buckets:
            sorted_list.extend(bucket)

        return sorted_list

    @staticmethod
    def block_sort(arr):
        """
        块排序（Block Sort）算法是一种外部排序算法，适用于处理大规模数据集的情况。

        参数：
        arr (list): 待排序的列表。

        返回：
        list: 排序后的列表。

        稳定性：
        是稳定排序算法。
        原因：块排序中，相同元素的相对顺序不会改变。

        实现步骤：
        1. 将待排序的数据划分为多个块，每个块的大小适应内存限制。
        2. 对每个块内的数据进行排序。
        3. 将排序后的块写入磁盘。
        4. 依次读取每个块的首个元素，选择最小的元素放入有序序列。
        5. 重复步骤4，直到所有块的元素都放入有序序列。

        """

        def merge_sorted_blocks(blocks):
            """
            合并多个已排序的块。

            参数：
            blocks (list): 多个已排序的块。

            返回：
            list: 合并后的有序序列。
            """
            sorted_list = []

            while blocks:
                min_val = float("inf")
                min_block_idx = -1

                # 找到最小元素所在的块
                for i, block in enumerate(blocks):
                    if block and block[0] < min_val:
                        min_val = block[0]
                        min_block_idx = i

                # 将最小元素从块中取出
                min_val = blocks[min_block_idx].pop(0)
                sorted_list.append(min_val)

                # 如果块为空，则从列表中移除该块
                if not blocks[min_block_idx]:
                    blocks.pop(min_block_idx)

            return sorted_list

        # 步骤 1: 将待排序的数据划分为多个块，每个块的大小适应内存限制
        block_size = 4
        num_blocks = (len(arr) + block_size - 1) // block_size

        blocks = [[] for _ in range(num_blocks)]

        # 步骤 2: 对每个块内的数据进行排序，并将排序后的块写入磁盘
        for i in range(num_blocks):
            start = i * block_size
            end = start + block_size
            block = arr[start:end]
            block.sort()
            blocks[i] = block

        # 步骤 4: 依次读取每个块的首个元素，选择最小的元素放入有序序列
        sorted_list = merge_sorted_blocks(blocks)

        return sorted_list


    @staticmethod
    def external_sort(arr):
        """
        外部排序算法是一种用于处理大规模数据集的排序算法，它利用外部存储器（例如磁盘）来对数据进行排序。

        参数：
        arr (list): 待排序的列表。

        返回：
        list: 排序后的列表。

        稳定性：
        不是稳定排序算法。
        原因：外部排序中，相同元素的相对顺序可能会改变。

        实现思路：
        1. 将待排序的数据划分为多个块，每个块的大小适应内存限制。
        2. 对每个块内的数据进行排序。
        3. 将排序后的块写入磁盘。
        4. 依次读取每个块的首个元素，选择最小的元素放入有序序列。
        5. 重复步骤 4，直到所有块的元素都放入有序序列。

        """

        # 步骤 1: 将待排序的数据划分为多个块，每个块的大小适应内存限制
        block_size = 4
        num_blocks = (len(arr) + block_size - 1) // block_size

        # 步骤 2: 对每个块内的数据进行排序，并将排序后的块写入磁盘
        for i in range(num_blocks):
            start = i * block_size
            end = start + block_size
            block = arr[start:end]
            block.sort()
            # 将排序后的块写入磁盘，这里只是模拟写入操作

        # 步骤 3: 依次读取每个块的首个元素，选择最小的元素放入有序序列
        sorted_list = []
        blocks = [[] for _ in range(num_blocks)]
        # 这里只是模拟从磁盘读取块的操作
        for i in range(num_blocks):
            # 从磁盘读取块并放入内存的对应位置
            blocks[i] = arr[i * block_size: (i + 1) * block_size]

        # 重复步骤 4，直到所有块的元素都放入有序序列
        while any(blocks):
            min_val = float('inf')
            min_block_idx = -1
            # 选择最小的元素
            for i in range(num_blocks):
                if blocks[i] and blocks[i][0] < min_val:
                    min_val = blocks[i][0]
                    min_block_idx = i
            # 将最小元素放入有序序列
            sorted_list.append(blocks[min_block_idx].pop(0))
            # 如果块中的元素已全部取完，则移除该块
            if not blocks[min_block_idx]:
                blocks.pop(min_block_idx)
                num_blocks -= 1

        return sorted_list

# 主程序示例
if __name__ == "__main__":
    # 创建随机输入列表
    input_list = [random.randint(0, 10) for _ in range(5)]
    print(f"input_list: {input_list}")

    # 混排（Shuffle Sort）
    shuffled_list = OtherSort.shuffle_sort(input_list)
    print("Shuffled List:", shuffled_list)

    # 睡眠排序（Sleep Sort）
    sorted_list = OtherSort.sleep_sort(input_list)
    print("Sleep List:", sorted_list)

    # 环排序（Cycle Sort）
    # sorted_list = OtherSort.cycle_sort(input_list)
    # print("Cycle List:", sorted_list)

    # 鸡尾酒排序（Cocktail Sort）
    sorted_list = OtherSort.cocktail_sort(input_list)
    print("Cocktail List:", sorted_list)

    # 梳排序（Comb Sort）
    sorted_list = OtherSort.comb_sort(input_list)
    print("Comb List:", sorted_list)

    # 计算机科学家排序（Bogo Sort）
    sorted_list = OtherSort.bogo_sort(input_list)
    print("Sorted List:", sorted_list)

    # 木桶排序（Bucket Sort）
    sorted_list = OtherSort.bucket_sort(input_list)
    print("Bogo List:", sorted_list)

    # 块排序（Block Sort）
    sorted_list = OtherSort.block_sort(input_list)
    print("Block List:", sorted_list)

    # 外部排序（External Sort）
    sorted_list = OtherSort.external_sort(input_list)
    print("External List:", sorted_list)
